Stack

06 Aug 2022 in Study / Computer science on Stack

Data Structure, 이것이 자료구조+알고리즘이다 with C언어 (reference), OOP course in Yonsei

• A kind of data structure
• LIFO (Last in, First out)

Basic Method

• push : storing data in Stack
• pop : bring the top datum and remove it
• peek : just bring the top datum

Stack In Java

• provide Stack generic class by java.util

import java.util.Stack

public class stackpractice {

  public static void main(String[] args) {
    Stack<Integer> s = new Stack<Integer>();

    s.push(1);     // s == [1]
    s.push(2);     // s == [1, 2]
    s.push(3);     // s == [1, 2, 3]

    int i = s.pop();    // i == 3, s == [1, 2]
    i = s.peek();       // i == 2, s == [1, 2]
    System.out.println(s) // s.toString() → [1, 2]
    System.out.println(s.search(2)) // 1
    // search(Object o) → if o is lacated on top , 1
    System.out.println(s.isEmpty()) // false
  }

}

Stack In Python

• not provide Stack
• We can implement Stack by list, Class, and Deque
• List
  • append() : push
  • pop()
• Class

  class Stack:
    def __init__(self):
      self.stack = []
    def push(self, s):
      self.stack.append(s)
    def pop(self):
      return self.stack.pop()
    def isEmpty():
      return len(self.stack) == 0
    def peek():
      return self.stack[0]
  
  

• go Queue posting for deque

Stack In C (Array)

• Stack can be implemented by array
• We have to set the capacity before making stack
• push & pop are implemented by just controlling the integer value which represents top value of the stack
  • Consequently, there is no real addition or deletion
• struct stack
  • It has to involve the capacity and top (int)
  • Let the element going to push into stack integer (example)
  • int* data -> array for integer values

typedef struct stack
{
    int capacity;
    int top;
    int* data;
} ArrayStack;

• createStack
  • For 1-D pointer modification, this function needs to involve 2-D pointer parameter (ArrayStack** stack)
  • If stack and (stack)->Data get value through static assignment, it will be stored in “createStack” region in stack memory
    • It will be deleted when “createStack” function finishes
    • Consequently, we need to store it into heap memory that programmer can deallocate it in anytime (Dynamic assignment)
  • capacity initialization
  • top has to have -1 value at first (As pushing the elements, 1 adds to top)

void createStack(ArrayStack** stack, int capacity)
{
    *stack = (ArrayStack*)malloc(sizeof(ArrayStack));
    (*stack)->capacity = capacity;
    (*stack)->top = -1;
    (*stack)->data = (int*)malloc(sizeof(int) * capacity);
}

• destroyStack
  • For deallocating (*stack)->data and *stack
  • The order of using free is important
  • free deallocate the data which are pointed by pointer
    • After using free, the pointer has still address
    • Consequently, it is desired to let pointer have NULL value after deallocating

void destroyStack(ArrayStack** stack)
{
    free((*stack)->data);
    (*stack)->data = NULL;
    free(*stack);
    *stack = NULL;
}

• push
  • add 1 to top
  • just set newData to top location of stack array

void push(ArrayStack* stack, int newData)
{
    stack->top++;
    stack->data[stack->top] = newData;
}

• pop
  • get the current top value (currentTop) and use it for getting the top value of stack
  • subtract 1 from top value

int pop(ArrayStack* stack)
{
    int currentTop = stack->top--;
    return stack->data[currentTop];
}

• getTop
  • getting the top value of stack
• getSize
  • getting current size of stack
• isEmpty
  • check whether stack has value or not

int getTop(ArrayStack* stack)
{
    return stack->data[stack->top];
}

int getSize(ArrayStack* stack)
{
    return (stack->top) + 1;
}

int isEmpty(ArrayStack* stack)
{
    return (stack->top) == -1;
}

Stack In C (Linked List)

• Stack can be implemented by linked list
• Node struct (The element of linked list)
  • single linked list (just example)
  • Let the data in linked list be String (char*)

typedef struct node
{
    char* data;
    struct node* nextNode;
} Node;

• Stack struct
  • list : head node (Consequently, it represents the whole linked list)
  • tail : tail node (Consequently, it represents the top node of the stack)

typedef struct stack
{
    Node* list;
    Node* tail;
} LinkedListStack;

• We need two kinds of function for Stack creation & Node creation (createStack & createNode)
  • For same reason, stack needs to be made by dynamic assignment
  • For same reason, node and node’s data have to be made by dynamic assignment

void createStack(LinkedListStack** stack)
{
    *stack = (LinkedListStack*)malloc(sizeof(LinkedListStack));
    (*stack)->list = NULL;
    (*stack)->tail = NULL;

}

Node* createNode(char* data)
{
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = (char*)malloc(strlen(data) + 1);

    strcpy(newNode->data, data);
    newNode->nextNode = NULL;

    return newNode;
}

• We need two kinds of function for Stack destruction & Node destruction (destroyStack & destroyNode)
  • destroyStack : If there are left nodes, it has to be deleted and deallocated
  • destroyNode : Deallocation order is important

void destroyStack(LinkedListStack** stack)
{
    while (!isEmpty(*stack))
    {
        Node* popNode = pop(*stack);
        destroyNode(&popNode);
    }
    free(*stack);
    *stack = NULL;
}

void destroyNode(Node** node)
{
    free((*node)->data);
    (*node)->data = NULL;
    free(*node);
    *node = NULL;
}

• push
  • After pushing the new node, top node has to be updated

void push(LinkedListStack* stack, Node* newNode)
{
    if (stack->list == NULL)
    {
        stack->list = newNode;
    }
    else
    {
        stack->tail->nextNode = newNode;
    }
    stack->tail = newNode;
}

• pop
  • 1^st : Deletion of the top node
    • Top == Head : list & tail have to be NULL
    • Approach the top node through linear search (if we made doubly linked list, we don’t need to use it) and delete it
  • 2^nd : return topNode

Node* pop(LinkedListStack* stack)
{
    Node* topNode = stack->tail;

    if (stack->list == stack->tail)
    {
        stack->list = NULL;
        stack->tail = NULL;
    }
    else
    {
        Node* currentNode = stack->list;

        while (currentNode != NULL && currentNode->nextNode != stack->tail)
        {
            currentNode = currentNode->nextNode;
        }

        currentNode->nextNode = NULL;
        stack->tail = currentNode;
    }

    return topNode;
}

• getTop, getSize, isEmpty

char* getTop(LinkedListStack* stack)
{
    return stack->tail->data;
}

int getSize(LinkedListStack* stack)
{
    Node* currentNode = stack->list;
    int n = 0;

    while (currentNode != NULL)
    {
        n++;
        currentNode = currentNode->nextNode;
    }

    return n;
}

int isEmpty(LinkedListStack* stack)
{
    return (stack->list) == NULL;
}

Stack In C (Array vs Linked List)

• Array
  • push & pop are more efficient than linked list because it is implemented by just controlling the value of stack->top
  • It is hard to change capacity
• Linked List
  • There is no limitation (considering only stack situation) for pushing the elements because there is no concept of the capacity
  • push & pop are less efficient than array