Stack and Queue implementation in C++

Stack (also known as LIFO) and Queue(also known as FIFO) are two abstract data types in computer science that serve as collection of elements.

There are some specific operations associated with these two data types:

1. Push
2. Pop

Third operation is basically 'look up' (to see the top element in stack/queue).

All these three operations should take O(1) to process.

To know details of stack and queue, you can look up wikipedia[1][2]  to know more.

I am here to show you the implementation of these two in C++.

I am using linked list to implement it. Linked list has usual properties : node, head and link

---

Stack:

using namespace std;
class Stack{
public:
Stack* next;   // link between two nodes
Stack* head=NULL; // to gateway to enter the linked list (in this case our stack)
int data;
void push(int data){
Stack* s=new Stack();    // create a new node
s->data=data;
s->next=head;
head=s;
}
void pop(){
head=head->next;
}
int top(){
return head->data;
}
};

int main(){
Stack* s=new Stack();
s->push(12);
s->push(19);
s->push(23);
s->push(34);
s->pop();
cout << s->top() << endl;
return 0;
}

---

Queue:

#include <iostream>
using namespace std;
class Queue{
public:
Queue* next;
Queue* head=NULL;
Queue* tail=NULL;  // so that new element can be added to the queue in O(1) time.
int data;
void push(int data){
Queue* q=new Queue();
q->data=data;
q->next=NULL;
if(head==NULL){
head=q;
tail=q;
}else{
tail->next=q;
tail=q;
}
}
void pop(){
head=head->next;
}
int top(){
return head->data;
}
};

int main(){
Queue* q=new Queue();
q->push(12);
q->push(19);
q->push(23);
q->push(34);
q->pop();
q->pop();
cout << q->top() << endl;
return 0;
}

If I missed something, please let me know.
Happy coding !

---

Terms used in the blog:

LIFO: Last in first out

FIFO: First in first out

Reference:
Stack
Queue
Abstract data types