Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
stack.h
Go to the documentation of this file.
1 /**
2  * @file stack.h
3  * @author danghai
4  * @brief This class specifies the basic operation on a stack as a linked list
5  **/
6 #ifndef DATA_STRUCTURES_STACK_H_
7 #define DATA_STRUCTURES_STACK_H_
8 
9 #include <cassert>
10 #include <iostream>
11 
12 /** Definition of the node as a linked-list
13  * \tparam Type type of data nodes of the linked list should contain
14  */
15 template <class Type>
16 struct node {
17  Type data; ///< data at current node
18  node<Type> *next; ///< pointer to the next ::node instance
19 };
20 
21 /** Definition of the stack class
22  * \tparam Type type of data nodes of the linked list in the stack should
23  * contain
24  */
25 template <class Type>
26 class stack {
27  public:
28  /** Show stack */
29  void display() {
30  node<Type> *current = stackTop;
31  std::cout << "Top --> ";
32  while (current != nullptr) {
33  std::cout << current->data << " ";
34  current = current->next;
35  }
37  std::cout << "Size of stack: " << size << std::endl;
38  }
39 
40  /** Default constructor*/
41  stack() {
42  stackTop = nullptr;
43  size = 0;
44  }
45 
46  /** Copy constructor*/
47  explicit stack(const stack<Type> &otherStack) {
48  node<Type> *newNode, *current, *last;
49 
50  /* If stack is no empty, make it empty */
51  if (stackTop != nullptr) {
52  stackTop = nullptr;
53  }
54  if (otherStack.stackTop == nullptr) {
55  stackTop = nullptr;
56  } else {
57  current = otherStack.stackTop;
58  stackTop = new node<Type>;
59  stackTop->data = current->data;
60  stackTop->next = nullptr;
61  last = stackTop;
62  current = current->next;
63  /* Copy the remaining stack */
64  while (current != nullptr) {
65  newNode = new node<Type>;
66  newNode->data = current->data;
67  newNode->next = nullptr;
68  last->next = newNode;
69  last = newNode;
70  current = current->next;
71  }
72  }
73  size = otherStack.size;
74  }
75 
76  /** Destructor */
77  ~stack() {}
78 
79  /** Determine whether the stack is empty */
80  bool isEmptyStack() { return (stackTop == nullptr); }
81 
82  /** Add new item to the stack */
83  void push(Type item) {
84  node<Type> *newNode;
85  newNode = new node<Type>;
86  newNode->data = item;
87  newNode->next = stackTop;
88  stackTop = newNode;
89  size++;
90  }
91 
92  /** Return the top element of the stack */
93  Type top() {
94  assert(stackTop != nullptr);
95  return stackTop->data;
96  }
97 
98  /** Remove the top element of the stack */
99  void pop() {
100  node<Type> *temp;
101  if (!isEmptyStack()) {
102  temp = stackTop;
103  stackTop = stackTop->next;
104  delete temp;
105  size--;
106  } else {
107  std::cout << "Stack is empty !" << std::endl;
108  }
109  }
110 
111  /** Clear stack */
112  void clear() { stackTop = nullptr; }
113 
114  /** Overload "=" the assignment operator */
115  stack<Type> &operator=(const stack<Type> &otherStack) {
116  node<Type> *newNode, *current, *last;
117 
118  /* If stack is no empty, make it empty */
119  if (stackTop != nullptr) {
120  stackTop = nullptr;
121  }
122  if (otherStack.stackTop == nullptr) {
123  stackTop = nullptr;
124  } else {
125  current = otherStack.stackTop;
126  stackTop = new node<Type>;
127  stackTop->data = current->data;
128  stackTop->next = nullptr;
129  last = stackTop;
130  current = current->next;
131  /* Copy the remaining stack */
132  while (current != nullptr) {
133  newNode = new node<Type>;
134  newNode->data = current->data;
135  newNode->next = nullptr;
136  last->next = newNode;
137  last = newNode;
138  current = current->next;
139  }
140  }
141  size = otherStack.size;
142  return *this;
143  }
144 
145  private:
146  node<Type> *stackTop; /**< Pointer to the stack */
147  int size; ///< size of stack
148 };
149 
150 #endif // DATA_STRUCTURES_STACK_H_
stack::pop
void pop()
Definition: stack.h:99
std::srand
T srand(T... args)
stack::stack
stack(const stack< Type > &otherStack)
Definition: stack.h:47
data_structures::Node::Node
Node(int key, int level, void *value=nullptr)
Definition: skip_list.cpp:44
std::shared_ptr< Node >
data_structures::SkipList::displayList
void displayList()
Definition: skip_list.cpp:191
data_structures::SkipList::level
int level
Maximum level of the skiplist.
Definition: skip_list.cpp:56
data_structures::MAX_LEVEL
constexpr int MAX_LEVEL
Maximum level of skip list.
Definition: skip_list.cpp:27
data_structures::SkipList
Definition: skip_list.cpp:55
std::vector
STL class.
std::stack
STL class.
node
Definition: avltree.cpp:13
node
struct list node
std::queue
STL class.
main
int main()
Definition: skip_list.cpp:212
std::vector::push_back
T push_back(T... args)
data_structures::Node
Definition: skip_list.cpp:33
std::cout
data_structures::Node::value
void * value
pointer of value
Definition: skip_list.cpp:35
stack_linkedList
Definition: queue_using_linkedlist.cpp:10
queue_test
void queue_test()
Definition: queue_using_two_stacks.cpp:101
std::array
STL class.
linkedlist
Definition: queue_using_linkedlist.cpp:6
data_structures
Data Structures algorithms.
stack::push
void push(Type item)
Definition: stack.h:83
data_structures::Node::key
int key
key integer
Definition: skip_list.cpp:34
stack::size
int size
size of stack
Definition: stack.h:147
std::rand
T rand(T... args)
data_structures::SkipList::SkipList
SkipList()
Definition: skip_list.cpp:64
node::next
node< Type > * next
pointer to the next node instance
Definition: stack.h:18
stack::top
Type top()
Definition: stack.h:93
data
int data[MAX]
test data
Definition: hash_search.cpp:24
main
int main()
Definition: queue_using_two_stacks.cpp:141
std::endl
T endl(T... args)
stack::stack
stack()
Definition: stack.h:41
data_structures::Node::forward
std::vector< std::shared_ptr< Node > > forward
nodes of the given one in all levels
Definition: skip_list.cpp:37
stack::operator=
stack< Type > & operator=(const stack< Type > &otherStack)
Definition: stack.h:115
data_structures::SkipList::deleteElement
void deleteElement(int key)
Definition: skip_list.cpp:133
std
STL namespace.
show
void show(const struct tower *const F, const struct tower *const T, const struct tower *const U)
Definition: tower_of_hanoi.cpp:19
data_structures::SkipList::randomLevel
int randomLevel()
Definition: skip_list.cpp:75
stack
Definition: stack.h:26
Queue_Array
Definition: queue_using_array.cpp:13
stack::display
void display()
Definition: stack.h:29
stack::isEmptyStack
bool isEmptyStack()
Definition: stack.h:80
node::data
Type data
data at current node
Definition: stack.h:17
std::time
T time(T... args)
stack::stackTop
node< Type > * stackTop
Definition: stack.h:146
data_structures::SkipList::header
std::shared_ptr< Node > header
Pointer to the header node.
Definition: skip_list.cpp:57
stack::~stack
~stack()
Definition: stack.h:77
push
void push(char ch)
push byte to stack variable
Definition: paranthesis_matching.cpp:26
pop
char pop()
pop a byte out of stack variable
Definition: paranthesis_matching.cpp:29
std::cin
data_structures::PROBABILITY
constexpr float PROBABILITY
Current probability for "coin toss".
Definition: skip_list.cpp:28
data_structures::SkipList::searchElement
void * searchElement(int key)
Definition: skip_list.cpp:170
data_structures::SkipList::insertElement
void insertElement(int key, void *value)
Definition: skip_list.cpp:90
std::exit
T exit(T... args)
stack::clear
void clear()
Definition: stack.h:112
std::next
T next(T... args)
main
int main()
Definition: graph_coloring.cpp:96