Stack

• 概念

  • linear data structure which follows a particular order in which the operations are performed.

  • 順序: LIFO(後進先出) or FILO(先進後出)

• 主要Function

  • Push: 加入item到stack中, 如果stack已滿, 稱為overflow condition

  • Pop: 從stack中移除item, 如果stack已空, 稱為underflow condition

  • IsEmpty: return true if stack is empty.

  

• Implement stack

  • using array (C++ code)

  • using linked list (C code)

• C++

     /* C++ program to implement basic stack
       operations */
    #include<bits/stdc++.h>
    using namespace std;
  
    #define MAX 1000
  
    class Stack
    {
            int top;
        public:
            int a[MAX];    //Maximum size of Stack
            Stack()  { top = -1; }
            bool push(int x);
            int pop();
            bool isEmpty();
    };
  
    bool Stack::push(int x)
    {
        if (top >= MAX)
        {
            cout << "Stack Overflow";
            return false;
        }
        else
        {
            a[++top] = x;
            return true;
    }
    }
  
    int Stack::pop()
    {
        if (top < 0)
        {
            cout << "Stack Underflow";
            return 0;
        }
        else
        {
            int x = a[top--];
            return x;
        }
    }
  
    bool Stack::isEmpty()
    {
        return (top < 0);
    }
  
    // Driver program to test above functions
    int main()
    {
        struct Stack s;
        s.push(10);
        s.push(20);
        s.push(30);
  
        cout << s.pop() << " Popped from stack\n";
  
        return 0;
    }

• C

        // C program for linked list implementation of stack
        #include <stdio.h>
        #include <stdlib.h>
        #include <limits.h>
  
        // A structure to represent a stack
        struct StackNode
        {
            int data;
            struct StackNode* next;
        };
        struct StackNode* newNode(int data)
        {
            struct StackNode* stackNode = (struct StackNode*) malloc(sizeof(struct StackNode));
            stackNode->data = data;
            stackNode->next = NULL;
            return stackNode;
        }
        int isEmpty(struct StackNode *root)
        {
            return !root;
        }
  
        void push(struct StackNode** root, int data)
        {
            struct StackNode* stackNode = newNode(data);
            /*
            * 將新node的下一個node指向array[0]
            */
            stackNode->next = root[0];
  
            /*
            * 將新node的值assign給array[0]
            */                
            root[0] = stackNode;
            printf("%d pushed to stack\n", data);
        }
        int pop(struct StackNode** root)
        {
            /*
            * 如果array沒有node, 回傳INT_MIN
            */
            if (isEmpty(root[0]))
                return INT_MIN;
            /*
            * 新增一個temp node, 並將array[0]的值assign給temp node
            */ 
            struct StackNode* temp = root[0];
  
            /*
            * 將array[0]下一個node的值assign給array[0]
            */
            root[0] = (root[0])->next;
  
            /*
            * 回傳原array[0]的data
            */
            int popped = temp->data;
            free(temp);
            return popped;
        }
        int peek(struct StackNode* root)
        {
            if (isEmpty(root))
                return INT_MIN;
            return root->data;
        }
  
        int main()
        {
            struct StackNode* root = NULL;
  
            push(&root, 10);
            push(&root, 20);
            push(&root, 30);
  
            printf("%d popped from stack\n", pop(&root));
  
            printf("Top element is %d\n", peek(root));        
  
            return 0;
        }

• Reference from

  • http://quiz.geeksforgeeks.org/stack-data-structure/