8000 feat: add Dynamic Stack implementation (#1261) · khoih-prog/C_Algorithm@e278f5d · GitHub
[go: up one dir, main page]
Skip to content
< 8000 /div>

Commit e278f5d

Browse files
SahilK-027Panquesito7
SahilK-027
and
Panquesito7
authored
feat: add Dynamic Stack implementation (TheAlgorithms#1261)
* Create dynamic_stack.c In this implementation, functions such as PUSH, POP, PEEK, show_capacity, isempty, and stack_size are coded to implement dynamic stack. * Update dynamic_stack.c Worked on Suggested Changes. * Update dynamic_stack.c Worked on suggested changes. * Update dynamic_stack.c * Update: Used Int type that are OS-independent --------- Co-authored-by: David Leal <halfpacho@gmail.com>
1 parent 01bc982 commit e278f5d

File tree

1 file changed

+250
-0
lines changed

1 file changed

+250
-0
lines changed

‎data_structures/stack/dynamic_stack.c

Lines changed: 250 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,250 @@
1+
/**
2+
* @file
3+
*
4+
* @brief
5+
* Dynamic [Stack](https://en.wikipedia.org/wiki/Stack_(abstract_data_type)),
6+
* just like Dynamic Array, is a stack data structure whose the length or
7+
* capacity (maximum number of elements that can be stored) increases or
8+
* decreases in real time based on the operations (like insertion or deletion)
9+
* performed on it.
10+
*
11+
* In this implementation, functions such as PUSH, POP, PEEK, show_capacity,
12+
* isempty, and stack_size are coded to implement dynamic stack.
13+
*
14+
* @author [SahilK-027](https://github.com/SahilK-027)
15+
*
16+
*/
17+
#include <assert.h> /// to verify assumptions made by the program and print a diagnostic message if this assumption is false.
18+
#include <inttypes.h> /// to provide a set of integer types with universally consistent definitions that are operating system-independent
19+
#include <stdio.h> /// for IO operations
20+
#include <stdlib.h> /// for including functions involving memory allocation such as `malloc`
21+
/**
22+
* @brief DArrayStack Structure of stack.
23+
*/
24+
typedef struct DArrayStack
25+
{
26+
int capacity, top; ///< to store capacity and top of the stack
27+
int *arrPtr; ///< array pointer
28+
} DArrayStack;
29+
30+
/**
31+
* @brief Create a Stack object
32+
*
33+
* @param cap Capacity of stack
34+
* @return DArrayStack* Newly created stack object pointer
35+
*/
36+
DArrayStack *create_stack(int cap)
37+
{
38+
DArrayStack *ptr;
39+
ptr = (DArrayStack *)malloc(sizeof(DArrayStack));
40+
ptr->capacity = cap;
41+
ptr->top = -1;
42+
ptr->arrPtr = (int *)malloc(sizeof(int) * cap);
43+
printf("\nStack of capacity %d is successfully created.\n", ptr->capacity);
44+
return (ptr);
45+
}
46+
47+
/**
48+
* @brief As this is stack implementation using dynamic array this function will
49+
* expand the size of the stack by twice as soon as the stack is full.
50+
*
51+
* @param ptr Stack pointer
52+
* @param cap Capacity of stack
53+
* @return DArrayStack*: Modified stack
54+
*/
55+
DArrayStack *double_array(DArrayStack *ptr, int cap)
56+
{
57+
int newCap = 2 * cap;
58+
int *temp;
59+
temp = (int *)malloc(sizeof(int) * newCap);
60+
for (int i = 0; i < (ptr->top) + 1; i++)
61+
{
62+
temp[i] = ptr->arrPtr[i];
63+
}
64+
free(ptr->arrPtr);
65+
ptr->arrPtr = temp;
66+
ptr->capacity = newCap;
67+
return ptr;
68+
}
69+
70+
/**
71+
* @brief As this is stack implementation using dynamic array this function will
72+
* shrink the size of stack by twice as soon as the stack's capacity and size
73+
* has significant difference.
74+
*
75+
* @param ptr Stack pointer
76+
* @param cap Capacity of stack
77+
* @return DArrayStack*: Modified stack
78+
*/
79+
DArrayStack *shrink_array(DArrayStack *ptr, int cap)
80+
{
81+
int newCap = cap / 2;
82+
int *temp;
83+
temp = (int *)malloc(sizeof(int) * newCap);
84+
for (int i = 0; i < (ptr->top) + 1; i++)
85+
{
86+
temp[i] = ptr->arrPtr[i];
87+
}
88+
free(ptr->arrPtr);
89+
ptr->arrPtr = temp;
90+
ptr->capacity = newCap;
91+
return ptr;
92+
}
93+
94+
/**
95+
* @brief The push function pushes the element onto the stack.
96+
*
97+
* @param ptr Stack pointer
98+
* @param data Value to be pushed onto stack
99+
* @return int Position of top pointer
100+
*/
101+
int push(DArrayStack *ptr, int data)
102+
{
103+
if (ptr->top == (ptr->capacity) - 1)
104+
{
105+
ptr = double_array(ptr, ptr->capacity);
106+
ptr->top++;
107+
ptr->arrPtr[ptr->top] = data;
108+
}
109+
else
110+
{
111+
ptr->top++;
112+
ptr->arrPtr[ptr->top] = data;
113+
}
114+
printf("Successfully pushed : %d\n", data);
115+
return ptr->top;
116+
}
117+
118+
/**
119+
* @brief The pop function to pop an element from the stack.
120+
*
121+
* @param ptr Stack pointer
122+
* @return int Popped value
123+
*/
124+
int pop(DArrayStack *ptr)
125+
{
126+
if (ptr->top == -1)
127+
{
128+
printf("Stack is empty UNDERFLOW \n");
129+
return -1;
130+
}
131+
int ele = ptr->arrPtr[ptr->top];
132+
ptr->arrPtr[ptr->top] = 0;
133+
ptr->top = (ptr->top - 1);
134+
if ((ptr->capacity) % 2 == 0)
135+
{
136+
if (ptr->top <= (ptr->capacity / 2) - 1)
137+
{
138+
ptr = shrink_array(ptr, ptr->capacity);
139+
}
140+
}
141+
printf("Successfully popped: %d\n", ele);
142+
return ele;
143+
}
144+
145+
/**
146+
* @brief To retrieve or fetch the first element of the Stack or the element
147+
* present at the top of the Stack.
148+
*
149+
* @param ptr Stack pointer
150+
* @return int Top of the stack
151+
*/
152+
int peek(DArrayStack *ptr)
153+
{
154+
if (ptr->top == -1)
155+
{
156+
printf("Stack is empty UNDERFLOW \n");
157+
return -1;
158+
}
159+
return ptr->arrPtr[ptr->top];
160+
}
161+
162+
/**
163+
* @brief To display the current capacity of the stack.
164+
*
165+
* @param ptr Stack pointer
166+
* @return int Current capacity of the stack
167+
*/
168+
int show_capacity(DArrayStack *ptr) { return ptr->capacity; }
169+
170+
/**
171+
* @brief The function is used to check whether the stack is empty or not and
172+
* return true or false accordingly.
173+
*
174+
* @param ptr Stack pointer
175+
* @return int returns 1 -> true OR returns 0 -> false
176+
*/
177+
int isempty(DArrayStack *ptr)
178+
{
179+
if (ptr->top == -1)
180+
{
181+
return 1;
182+
}
183+
return 0;
184+
}
185+
186+
/**
187+
* @brief Used to get the size of the Stack or the number of elements present in
188+
* the Stack.
189+
*
190+
* @param ptr Stack pointer
191+
* @return int size of stack
192+
*/
193+
int stack_size(DArrayStack *ptr) { return ptr->top + 1; }
194+
195+
/**
196+
* @brief Self-test implementations
197+
* @returns void
198+
*/
199+
static void test()
200+
{
201+
DArrayStack *NewStack;
202+
int capacity = 1;
203+
NewStack = create_stack(capacity);
204+
uint64_t arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
205+
206+
printf("\nTesting Empty stack: ");
207+
assert(stack_size(NewStack) == 0);
208+
assert(isempty(NewStack) == 1);
209+
printf("Size of an empty stack is %d\n", stack_size(NewStack));
210+
211+
printf("\nTesting PUSH operation:\n");
212+
for (int i = 0; i < 12; ++i)
213+
{
214+
int topVal = push(NewStack, arr[i]);
215+
printf("Size: %d, Capacity: %d\n\n", stack_size(NewStack),
216+
show_capacity(NewStack));
217+
assert(topVal == i);
218+
assert(peek(NewStack) == arr[i]);
219+
assert(stack_size(NewStack) == i + 1);
220+
assert(isempty(NewStack) == 0);
221+
}
222+
223+
printf("\nTesting POP operation:\n");
224+
for (int i = 11; i > -1; --i)
225+
{
226+
peek(NewStack);
227+
assert(peek(NewStack) == arr[i]);
228+
int ele = pop(NewStack);
229+
assert(ele == arr[i]);
230+
assert(stack_size(NewStack) == i);
231+
}
232+
233+
printf("\nTesting Empty stack size: ");
234+
assert(stack_size(NewStack) == 0);
235+
assert(isempty(NewStack) == 1);
236+
printf("Size of an empty stack is %d\n", stack_size(NewStack));
237+
238+
printf("\nTesting POP operation on empty stack: ");
239+
assert(pop(NewStack) == -1);
240+
}
241+
242+
/**
243+
* @brief Main function
244+
* @returns 0 on exit
245+
*/
246+
int main()
247+
{
248+
test(); // run self-test implementations
249+
return 0;
250+
}

0 commit comments

Comments
 (0)
0